/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package org.fjala.softure.tree.array;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import org.fjala.softure.tree.Node;
import org.fjala.softure.tree.Tree;

/**
 * This tree manages its children in a Array.
 *
 * @author Jorge Lopez
 * @author Manolo Alvarez
 */
public class ArrayBinaryTree<T extends Comparable<T>> implements Tree<T> {

    /**
     * It is a root of the tree.
     */
    private ArrayBinaryNode<T> root;

    /**
     * Number of children.
     */
    private int count;

    /**
     * This constructor initializes this class with default values.
     */
    public ArrayBinaryTree() {
        root = new ArrayBinaryNode<T>(null);
    }

    /**
     * This constructor sets the root of the tree.
     */
    public ArrayBinaryTree(Node<T> root) {
        this.root = (ArrayBinaryNode<T>) root;
    }

    /**
     * Search a node in the tree.
     *
     * @param node to search.
     *
     * @return return null if .
     */
    private Node<T> searchByNode(Node<T> node) {
        ArrayBinaryNode resp = null;

        return search(resp, root, node.getData());
    }

    /**
     * Search a value in the tree.
     *
     * @param value to search.
     *
     * @return node found.
     */
    private Node<T> searchByValue(T value) {
        ArrayBinaryNode resp = null;

        return search(resp, root, value);
    }

    /**
     * Search a value in the tree Search a value in the tree.
     *
     * @param resp node found.
     * @param node parent.
     * @param value to search.
     *
     * @return node found.
     */
    private Node<T> search(Node<T> resp, Node<T> node, T value) {
        if (resp == null) {
            if (node.getData().equals(value)) {
                resp = node;
            } else {
                if (node.hasChildren()) {
                    List<Node<T>> children = node.getChildren();

                    for (Node child : children) {
                        if (child != null) {
                            resp = search(resp, child, value);
                        }
                    }
                }
            }
        }

        return resp;
    }

    @Override
    public void replace(T oldValue, T newValue) {
        Node found = searchByValue(oldValue);
        if (found != null) {
            found.setData(newValue);
        }
    }

    @Override
    public Node<T> getRoot() {
        return root;
    }

    @Override
    public int size() {
        return count;
    }

    @Override
    public boolean isEmpty() {
        return root.getChildren().isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        boolean resp = false;

        if (o instanceof Node) {
            if (searchByNode((Node) o) != null) {
                resp = true;
            }
        }

        return resp;
    }

    @Override
    public Iterator<T> iterator() {
        return new ArrayBinaryIterator<T>(root);
    }

    @Override
    public Object[] toArray() {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public <T> T[] toArray(T[] a) {
        throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public boolean add(T e) {
        ArrayBinaryNode<T> newNode = new ArrayBinaryNode<T>(e);

        if (root.getData() == null) {
            root = newNode;
        } else {
            add(root, newNode);
        }
        count++;
        return true;
    }

    /**
     * Adds a new node in the tree.
     * 
     * @param node is used to root node
     * @param newNode is used to new node
     */
    private void add(ArrayBinaryNode<T> node, ArrayBinaryNode<T> newNode) {
        if (node.getLeft() == null && node.getRight() == null) {
            node.setLeft(newNode);
        } else if (node.getRight() == null) {
            node.setRight(newNode);
        } else if (node.getLeft().getChildCount()
                <= node.getRight().getChildCount()) {
            add(node.getLeft(), newNode);
        } else {
            add(node.getRight(), newNode);
        }
    }

    @Override
    public boolean remove(Object o) {
        boolean resp = false;

        Node<T> found = searchByValue((T) o);

        if (found != null) {
            found.getParent().removeChild(found);
            resp = true;
        }

        return resp;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object object : c) {
            contains(object);
        }

        return true;
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        for (T e : c) {
            add(e);
        }

        return true;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        for (Object object : c) {
            remove(object);
        }

        return true;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        boolean modified = false;
	Iterator<T> e = iterator();
        
	while (e.hasNext()) {
	    if (!c.contains(e.next())) {
		e.remove();
		modified = true;
	    }
	}
	return modified;
    }

    @Override
    public void clear() {
        root = new ArrayBinaryNode<T>(null);
    }

    @Override
    public boolean add(Node<T> parent, T element) {
       ArrayBinaryNode<T> newNode = new ArrayBinaryNode<T>(element);
       parent.addChild(newNode);
       return true;
    }
}
